/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.acworks.acroute.v2.impl;

import com.acworks.acroute.v2.Arc;
import com.acworks.acroute.v2.ArcDirectionType;
import com.acworks.acroute.v2.ArcRequiredType;
import com.acworks.acroute.v2.ImmutableGraph;
import com.acworks.acroute.v2.Node;
import com.acworks.acroute.v2.Path;
import com.acworks.acroute.v2.PathAwareGraph;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

/**
 * view of original graph with directed arcs computed from the supplied partial path.
 * @author nikita
 */
public class PathAwareGraphImpl extends AbstractGraph implements PathAwareGraph {

    final private Set<Arc> requiredArcs;
    final private Path partialPath;

    public PathAwareGraphImpl(ImmutableGraph g, Path p) {
        super(new TreeSet<Node>(g.getNodes()));

        assert p != null;

        Set<Arc> arcClones = new HashSet<Arc>(g.getArcs().size());
        for (Arc arc : g.getArcs()) {
            Arc clone = new ArcImpl(arc);
            arcClones.add(clone);
        }
        setArcs(arcClones);

        this.partialPath = p;

        //initially all arcs are undecided
        this.requiredArcs = GraphUtil.findRequiredArcs(this, p);
        Set<Arc> updatedArcs = GraphUtil.updateArcDirections(this, requiredArcs);
        //delete all cache entries where related Nodes are part of cacheKey
        invalidateCacheEntries(updatedArcs);

        Set<Arc> arcsToDelete = GraphUtil.findUnneededArcs(this, requiredArcs);
        getArcs().removeAll(arcsToDelete);
        invalidateCacheEntries(arcsToDelete);
    }

    /**
     * @return collection of arcs required for any Hamiltonian Path containing specified partial path
     */
    @Override
    public Set<Arc> getRequiredArcs() {
        return requiredArcs;
    }

    @Override
    public Path getPartialPath() {
        return partialPath;
    }

    @Override
    public Set<Arc> getIncidentDirectedArcs(Node node, boolean orinating, ArcRequiredType requiredType) {
        Set<Arc> arcs = getIncidentDirectedArcs(node, orinating);
        if (requiredType != null) {
            switch (requiredType) {
                case NOT_REQUIRED:
                    arcs.removeAll(getRequiredArcs());
                    break;
                case REQUIRED:
                    arcs.retainAll(getRequiredArcs());
                    break;
                default:
                    throw new IllegalStateException("don't know how to handle type: " + requiredType);
            }

        }
        return arcs;
    }

    @Override
    public boolean isPartialPathAdmissible() {

        //test edges
        boolean failed = (!isConnected()) ||
                GraphUtil.isClosedNonHamiltonianCircuit(getRequiredArcs(), this);
        if (!failed) {
            for (Node n : getNodes()) {

                final Set<Arc> undirectedArcs = getIncidentArcs(n, ArcDirectionType.UNDIRECTED);

                int incomingArcCount = getIncidentDirectedArcs(n, false).size();
                int outgoingArcCount = getIncidentDirectedArcs(n, true).size();
                int undirectedArcCount = undirectedArcs.size();

                undirectedArcs.retainAll(requiredArcs);
                int undirectedRequiredArcCount = undirectedArcs.size();

                int incomingRequiredArcCount = getIncidentDirectedArcs(n, false, ArcRequiredType.REQUIRED).size();
                int outgoingRequiredArcCount = getIncidentDirectedArcs(n, true, ArcRequiredType.REQUIRED).size();

                int totalArcCount = incomingArcCount + outgoingArcCount + undirectedArcCount;
                int totalRequiredCount = incomingRequiredArcCount + outgoingRequiredArcCount + undirectedRequiredArcCount;


                failed = (totalArcCount <= 1) ||
                        (incomingArcCount == 0 && undirectedArcCount == 0) ||
                        (outgoingArcCount == 0 && undirectedArcCount == 0) ||
                        (incomingRequiredArcCount == 2) ||
                        (outgoingRequiredArcCount == 2) ||
                        (totalRequiredCount == 3);

                if (failed) {
                    break;
                }
            }
        }

        return !failed;
    }

    /**
     * 
     * @return true if this graph is connected 
     * (not subject to Rubin's F7-8 failure conditions)
     * 
     */
    public boolean isConnected() {
        Set<Node> flaggedNodes = new HashSet<Node>(partialPath.getPathNodes());
        Set<Node> wipSet = new HashSet<Node>();
        //put last node in wip list
        wipSet.add(partialPath.getPathNodes().get(partialPath.getPathNodes().size() - 1));

        while (!wipSet.isEmpty()) {
            Iterator<Node> wipIterator = wipSet.iterator();
            Node node = wipIterator.next();
            wipIterator.remove();
            Set<Node> successors = node.getSuccessors();

            Set<Node> wipAddition = new HashSet<Node>(successors);
            wipAddition.removeAll(flaggedNodes);
            flaggedNodes.addAll(successors);
            wipSet.addAll(wipAddition);
        }

        return flaggedNodes.equals(getNodes());
    }
}
